package retrospection.N皇后;

import java.util.ArrayList;
import java.util.List;

/**
 * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 * <p>
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * <p>
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 */
public class Solution {
    public List<List<String>> solveNQueens(int n) {
        /**
         * 设置数组 isPlace[n][n]表示是否可以放置皇后
         * 假设 r , c 表示n x n 棋盘的横纵坐标
         * 当有一个皇后在 r , c 处放置时 ，则有 isPlace[r][.....] 、 isPlace[.....][c] 、isPlace[r+x][c+x]处都不能再放置棋子了
         */
        List<List<String>> ans = new ArrayList<>();
        backtrack(n, new int[n][n], 0, ans, new ArrayList<>());
        return ans;
    }

    void backtrack(int n, int[][] isPlace, int r, List<List<String>> ans, List<String> temp) {
        if (n == 0) {
            ans.add(new ArrayList<>(temp));
        }
        if (r >= isPlace.length) {
            return;
        }
        for (int i = r; i < isPlace.length; i++) {
            int [] in = new int[isPlace.length];
            for (int j = 0; j < isPlace.length; j++) {
                if (isPlace[i][j] > 0) {
                    continue;
                }
                n--;
                in[j]  = 1 ;
                place(isPlace, i, j);
                temp.add(arrayToString(in));
                backtrack(n, isPlace, i + 1, ans, temp);
                temp.remove(temp.size() - 1);
                in[j] = 0 ;
                n++;
                backtrackPlace(isPlace, i, j);
            }
        }
    }

    void place(int[][] isPlace, int r, int c) {
        for (int i = 0; i < isPlace.length; i++) {
            isPlace[i][c]++;
        }
        for (int i = 0; i < isPlace.length; i++) {
            if (i == c) {
                continue;
            }
            isPlace[r][i]++;
        }
        for (int i = -r; r + i < isPlace.length && r + i >=0; i++) {
            if (i == 0) {
                continue;
            }
            if (c + i < isPlace.length && c + i >= 0){
                isPlace[r + i][c + i]++;
            }
        }
        for (int i = -r; r + i >= 0 && r + i < isPlace.length; i++) {
            if (i == 0) {
                continue;
            }
            if (c - i >= 0 && c - i < isPlace.length) {
                isPlace[r + i][c - i]++;
            }
        }
    }

    void backtrackPlace(int[][] isPlace, int r, int c) {
        for (int i = 0; i < isPlace.length; i++) {
            isPlace[i][c]--;
        }
        for (int i = 0; i < isPlace.length; i++) {
            if (i == c) {
                continue;
            }
            isPlace[r][i]--;
        }
        for (int i = -r; r + i < isPlace.length && r + i >=0; i++) {
            if (i == 0) {
                continue;
            }
            if (c + i < isPlace.length && c + i >= 0){
                isPlace[r + i][c + i]--;
            }
        }
        for (int i = -r; r + i >= 0 && r + i < isPlace.length; i++) {
            if (i == 0) {
                continue;
            }
            if (c - i >= 0 && c - i < isPlace.length) {
                isPlace[r + i][c - i]--;
            }
        }
    }

    String arrayToString(int [] ints){
        StringBuffer sb = new StringBuffer("");
        for (int i: ints) {
            if (i == 1){
                sb.append("Q");
            } else {
                sb.append(".");
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        List<List<String>> lists = new Solution().solveNQueens(6);
        for (List<String> list : lists) {
            for (String s : list) {
                System.out.println(s);
            }
            System.out.println("==========================================");
        }
    }
}
